package com.yitiao.data_algorithms.leetcode.editor.cn;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class ReverseLinkedListIi{
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null)return null;
        if (left == right) return head;
        int times = right - left + 1;
        ListNode prev  = head;
        for (int i = 1; i < left -1 ; i++) {
            prev =prev.next;
        }
        if (left!=1){
            prev.next = reverseList(prev.next,times);
            return head;
        }else {
            return reverseList(prev,times);
        }
    }
    private ListNode reverseList(ListNode head,int times) {
        ListNode cur = head;
        ListNode ans = null;
        int flag = 0;
        while (flag < times){
            ListNode next = cur.next;
            // 核心 拆下里的结点指向尾指针
            cur.next = ans;
            // 尾指针下移
            ans = cur;
            // 结点向下遍历
            cur = next;
            flag ++;
        }
        ListNode tail = ans;
        while (ans.next!=null){
            ans = ans.next;
        }
        ans.next = cur;
        return tail;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}